category: structure - data
诞生本无数据结构概念
数据结构
总览
概述
定义
数据结构是计算机存储、组织数据的方式。数据结构是指相互之间存在一种或多种特定关系的数据元素的集合。通常情况下，精心选择的数据结构可以带来更高的运行或者存储效率。数据结构往往同高效的检索算法和索引技术有关。
B = (D, R)
B = (D, R, O)
组成
数据结点
数据结点（数据元素），简称结点（node）：
描述一个独立事物的名称、数量、特征、性质的一组相关信息组成一个数据结点；
通常，一个节点含有多个数据项（data item）
- 结点的类型：结构型
- 关键字（key）
单值类型的结点：只含一个数据项
数据结点间的关系集
数据结点间的运算集
前三项（查找、插入、删除）为基本运算，后六项都可以通过前三项的组合实现。
查找（search）
插入（insert）
删除（delete）
存取（access）
更新（update）
合并（merge）
分裂（split）
复制（copy）
排序（sorting）
分类
表 - 一对一
树 - 一对多
图 - 多对多
散 - 无关
研究对象
数据的逻辑结构
数据的逻辑结构是从具体问题抽象出来的数学模型，反映数据元素之间的逻辑关系，其中的逻辑关系是指数据元素之间的前后件关系，而与他们在计算机中的存储位置无关；是描述数据元素及其关系的数学特性的，有时就把逻辑结构简称为数据结构。
逻辑结构是在计算机存储中的映像，形式地定义为（K，R）（或（D，S）），其中，K是数据元素的有限集，R是K上的关系的有限集。
数据结构中，逻辑上（逻辑结构：数据元素之间的逻辑关系）可以把数据结构分成线性结构和非线性结构。
逻辑结构与数据元素本身的形式、内容、相对位置、所含结点个数都无关。
数据的物理结构
指数据的逻辑结构在计算机存储空间的存放形式。
数据的物理结构是数据结构在计算机中的表示（又称映像），它包括数据元素的机内表示和关系的机内表示。由于具体实现的方法有顺序、链接、索引、散列等多种，所以，一种数据结构可表示成一种或多种存储结构。
数据元素的机内表示（映像方法）： 用二进制位（bit）的位串表示数据元素。通常称这种位串为节点（node）。当数据元素有若干个数据项组成时，位串中与各数据项对应的子位串称为数据域（data field）。因此，节点是数据元素的机内表示（或机内映像）。
关系的机内表示（映像方法）：数据元素之间的关系的机内表示可以分为顺序映像和非顺序映像，常用两种存储结构：顺序存储结构和链式存储结构。顺序映像借助元素在存储器中的相对位置来表示数据元素之间的逻辑关系。非顺序映像借助指示元素存储位置的指针来表示数据元素之间的逻辑关系。
顺序存储方法：它是把逻辑上相邻的结点存储在物理位置相邻的存储单元里，结点间的逻辑关系由存储单元的邻接关系来体现，由此得到的存储表示称为顺序存储结构。顺序存储结构是一种最基本的存储表示方法，通常借助于程序设计语言中的数组来实现。
链接存储方法：它不要求逻辑上相邻的结点在物理位置上亦相邻，结点间的逻辑关系是由附加的指针字段表示的。由此得到的存储表示称为链式存储结构，链式存储结构通常借助于程序设计语言中的指针类型来实现
散列存储方法：就是根据结点的关键字直接计算出该结点的存储地址。
为什么要学习“数据结构”
- 为了便于对数据进行操作以及算法的优化。
- 从编程水平上说，知道什么是好的算法，学会设计和选择好的算法，会很大程度上提高程序设计能力和初步的算法设计能力。
- 从能力素质培养上说，训练计算机思维能力和问题求解能力，提高认知水平。
抽象数据类型 - ADT
抽象数据类型：一个数学模型以及定义在该模型上的一组操作。抽象数据类型实际上就是对该数据结构的定义。因为它定义了一个数据的逻辑结构以及在此结构上的一组算法。抽象数据类型可用以下三元组表示：（D，S，P）。D是数据对象，S是D上的关系集，P是对D的基本操作集。ADT的定义为：
ADT 抽象数据类型名：{ 数据对象：（数据元素集合），数据关系：（数据关系二元组结合），基本操作：（操作函数的罗列）}；
ADT 抽象数据类型名：{ 数据对象：（数据元素集合），数据关系：（数据关系二元组结合），基本操作：（操作函数的罗列）}；
两个重要特性
数据结构的抽象和实现
数据的逻辑结构（logical form）
B = (D, R)
B = (D, R, O)
逻辑结构示例
数据的物理结构（physical form）
表结构
线性表（顺序表、链表、栈（顺序栈、链栈）、队（顺序队、链队））
散列表
线性表（linear list）
准确地描述表的定义
知道表的存储结构特征
掌握顺序表的描述方式
逻辑实现
D
具有 n(n >= 0) 个数据结点（元素）的序列 A = (a1, a2, ..., an)；数据集合可以为空。
R
先后次序
首结点和尾结点
表的长度
空表
前驱和后继（左邻和右邻）
有序表
O
物理实现
线性表采用顺序存储的方式存储就称之为顺序表。
顺序表是在计算机内存中以数组的形式保存的线性表。
顺序表是指用一组地址连续的存储单元依次存储数据元素的线性结构。
线性表采用指针链接的方式存储就称之为链表。
线性表是从逻辑结构的角度来说的，除了头和尾之外，它的每一个元素都只有一个前驱元素和一个后驱元素。
各种队列（单向、双向、循环队列），栈等都是线性表的不同例子。
而数组是从物理存贮的角度来说的，线性表可以用数组存贮也可以用链表来存贮。同样的队列和栈也可以用数组和链表存贮，各有利弊。具体使用时，根据具体情况选择。
顺序存储 - 顺序表（sequential list）
存储结点的逻辑次序与物理次序一致。
链式存储 - 链表（linked list）
存储结点的逻辑次序与物理次序不一致
顺序表和链表的优缺点及适用场合
顺序表：（1）优点：查找速度较快，查找方便
（2）缺点：动态操作困难
（3）适用于查找操作
链表：（1）优点：动态操作方便，方便扩展
（2）缺点：查询效率低，不利于查询
（3）适用于动态的删除， 插入等操作
顺序表：内存中地址连续
长度不可变更
支持随机查找 可以在O(1)内查找元素
适用于需要大量访问元素的 而少量增添/删除元素的程序
链表 ：内存中地址非连续
长度可以实时变化
不支持随机查找 查找元素时间复杂度O（n）
适用于需要进行大量增添/删除元素操作 而对访问元素无要求的程序
顺序表 - 类似数组
操作
查找
二分查找算法
插入
删除
链表
准确地描述表的链式存储结构
写出单向链表的指定位置插入和删除的程序段
知道链表的种类和作用
知道常用链表的特点和图示方法
能够写出单向加尾链表查找的算法
能够写出单向加头循环链表的删除算法
能够写出双向链表的插入和删除算法
能够写出构造有序链表的算法
定义
链表就是表头指针和一串相继链接的结点的总称。
特点
种类
链表的图示
单向链表结点结构的定义
结点的产生和回收
操作
结点的链接操作
查找
单向加尾链表的查找
插入
删除
单向加头循环链表的删除
构造有序链表
栈
能够准确描述栈的特点
能够写出顺序栈的入栈和出栈算法
能够写出链栈的入栈和出栈算法
能够准确描述栈在程序中断中的作用
掌握简单算术表达式求值的方法
定义
只允许在同一端点出进行插入或删除的表结构称为栈（stack），栈是一种后进先出结构，又称为后进先出表（LIFO 表）。
术语
栈顶（top）：允许插入和删除的一端，top 指针总是指向栈顶。
栈底（bottom）：不允许插入和删除的一端。
进栈（push，压栈）：元素插入栈的过程。
出栈（pop，退栈）：从栈中弹出一个元素的过程。
栈空
栈满
栈溢出
栈的特点
后进先出，LIFO
栈的实例
子弹夹
浏览器的类似后退和前进按钮
函数之间的嵌套调用以及递归函数的执行
栈的物理实现
顺序栈
链栈
栈的应用
程序中断
中断：一个程序执行期间被其他程序所打断。
断点：被打断的地方。
现场（栈架）：被打断的程序当前的执行情况。
栈架与栈架之间服从后进先出的栈原则。
同一个栈架，数据存储的次序也遵守后进先出的栈原则。
保护现场和恢复现场。
嵌套中断的现场需要层层保护。
队列
能够准确描述队列的特点
能够写出顺序对的入队和出队算法
定义
允许在一端插入、另一端删除的表叫做队，或队列。
对结构好似一端两端开口的管道，结点从一端进入，从另一端退出。
对结构遵循先进先出原则，又称先进先出表（FIFO 表）。
术语
队尾（rear）：允许插入的一端
队头（front）：允许删除的一端
队满
队空
进队和出队：队的插入和删除
指针 first 和 last 分别指向队头和队尾，每当进队时移动尾指针，每当出队时移动首指针。
队的特点
先进先出（FIFO）
队的实例
排队买票
循环队（环形队 cyclic queue）
队的物理实现
顺序队
链式队
散列表
复述散列表的作用和意义
学会散列函数的设计方法
实现散列表的构造、插入和查找
选择并会使用开放地址法解决散列冲突
散列函数的设计原则
散列函数的设计方法
散列冲突
散列表的构造
树结构
什么是树
树的存储方法
能够准确复述树结构的相关术语
能够用图示和 C 语言描述树结构的存储方式
二叉树的基本概念和存储方法，区别不同的二叉树
能够用 C 语言描述二叉树的双链表的存储结构
能够准确图示森林、树、二叉树的相互转换
基本概念
定义
树是一种非线性的数据结构。
树是递归定义的，用来描述数据之间层次关系、分支关系和嵌套关系的基本数据结构。
术语
结点的度：当前结点所具有的子树的个数
树的元数：一棵树中，结点的度能允许的最大值
树叶：度数为 0 的结点（也称终端结点）
分枝点（内结点）：非叶结点
兄弟：同父的结点互为兄弟
结点的层数：根的层数定为 1；递推地，第 i 层结点的儿子层数为 i + 1
结点的高度：叶的高度定为 1；递推地，非叶结点的高度等于它各个儿子高度的最大值加 1
树高：等于其根结点的高度
有序树：树中结点的儿子按照某种次序排列
无序树：
位置树：一颗有序树中规定了每个结点儿子的位置
森林：树的集合，一个森林可包含 0 至多棵树
树的表示方法
计算机中树的存储方法
多重链接
儿子兄弟链
父亲链域
二叉树
定义
二叉树也称二分树，也称二元位置树：每个结点最多 2 个儿子，称为左、右儿子。
五种基本形态
二叉树的性质
二叉树的存储
| 静态存储 -- 顺序顺序法
补齐为完全二叉树，然后在按完全二叉树的存储方法存储
| 动态存储 -- 双链法
| 满二叉树
| 完全二叉树
完全二叉树是满二叉树的一部分；
满二叉树是完全二叉树的特例
| 非完全二叉树
补齐为完全二叉树，然后在按完全二叉树的存储方法存储
普通树与二叉树的相互转换
将复杂树的问题转换为简单二叉树的问题 -- 化繁为简
将树转换为二叉树
树中每个结点指向最左儿子的边不变
添加边，链接其紧挨着的第一个兄弟
去掉除链接的最左儿子的其余儿子的边，然后顺时针旋转 45度，即可得到二叉树
将二叉树转换为树
树转换为二叉树的逆过程
注意：
要转换为树的二叉树，其根结点没有右子树
森林与二叉树的转换
可以借助树与二叉树的转换来实现
森林转换为二叉树
二叉树转换为森林
二叉树的运算
查找 - 递归遍历
| 先根遍历
| 中根遍历
| 后根遍历
二叉树的构造
能够准确判断二叉树构造的唯一性条件
能够编程实现先（后）序、中序构造二叉树的递归算法
能够编程实现用扩充先序序列构造二叉树的递归算法
二叉树构造的问题
先（后）序序列、中序序列构造二叉树
扩充先（后）序序列唯一构造二叉树
二叉树 | 检索树
能够准确描述检索树的基本特征
能够编程实现检索树的查找、插入、构造、删除算法（递归、非递归）
什么是检索树
检索树的特点
左小右大
中序有序
检索树的查找
检索树的查询效率取决于树的高度
检索树的插入和构造
插入原则：简单、保中序
检索树的删除
原则：仅删除要删除的结点，并且保持中序有序
检索树的结点的三种情况：没有儿子，有一个儿子，有两个儿子
二叉树 | 检索树 | 平衡树
能够准确阐述平衡树的定义、性质
能够通过图示准确分析描述平衡树的插入、删除算法
能够准确图示给定平衡树的插入删除过程
二叉树 | 哈夫曼树
用于哈夫曼编码，无损压缩数据
什么是哈夫曼树
如何构造哈夫曼树
哈夫曼算法实现
哈夫曼编译和译码
应用实例
图结构
准确复述图的基本概念和相关术语
理解邻接矩阵的物理含义
准确掌握图的存储方法
定义
术语
顶点的度
子图
路径
回路：起点和终点相重合的简单路径
无向回路（圈）
有向回路
无向图的连通性
无向边
有向边
加权边
图的种类
邻接矩阵
散结构
如何利用高级语言描述存储结构
数组可以用来描述顺序存储
一个数组元素便是一个存储结点
下标作为结点的存储地址